package interview.kthlinear;

import java.util.Arrays;

public class KthLinear {
	public int run(int[] array, int k) {
		int left, right;
		left = 0;
		right = array.length - 1;
		while(true) {
			int pivotIndex = medianOfMedians(array); 
			pivotIndex = partition(array, left, right, pivotIndex);
			int pivotDist = pivotIndex - left + 1;
			if(pivotDist == k) {
				return array[pivotIndex];
			} else if(pivotDist < k) {
				left = pivotIndex + 1;
				k = k - pivotDist;
			} else {
				right = pivotIndex - 1;
			}
		}
	}
	
	public int medianOfMedians(int[] array) {
		if(array.length <= 5) {
			Arrays.sort(array);
			return array[2];
		}
				
		int numGroups = array.length / 5;
		int[] group = new int[5];
		int[] medians = new int[numGroups];
		for(int gid = 0; gid < numGroups; gid++) {
			for(int i = 0; i < 5; i++) {
				group[i] = array[i*numGroups+gid];
			}
			medians[gid] = medianOfMedians(group);
		}
		
		return medianOfMedians(medians);
	}

	private int partition(int[] array, int left, int right, int pivotIndex) {
		int buf = array[pivotIndex];
		array[pivotIndex] = array[right];
		array[right] = buf;
		
		int storeIndex = left;
		for(int i = left; i < right; i++) {
			if(array[i] < array[right]) {
				buf = array[i];
				array[i] = array[storeIndex];
				array[storeIndex] = buf;
				storeIndex++;
			}
		}
		
		buf = array[storeIndex];
		array[storeIndex] = array[right];
		array[right] = buf;
		
		return storeIndex;
	}
}
